#include <stdio.h>
#include <string.h>


int n, m, tot;
char ss[120][120];
char temp[120];
int  dd[120];
struct asdf
{
	int tot;
	int id;
}count[120];


main()
{
	int i,j,k,sum;

	memset(ss,0,sizeof(ss));
	memset(count,0,sizeof(count));

	
	scanf("%d%d", &n, &m);
	for (i=1;i<=m;i++)
	{
		scanf("%s", temp);
		memset(dd,0,sizeof(dd));		
		for (j=n-1,sum=0; j>=0; --j)
		{
			tot=0;
			for (k=j+1; k<n; ++k)
			{
				if (temp[j]==temp[k])	{ tot+=dd[k]; break;	}
				if (temp[j]>temp[k]) tot++;
			}
			dd[j]=tot;
			sum+=tot;
		}
		strcpy(ss[i],temp);
		count[i].id=i;
		count[i].tot=sum;
	}

	for (i=1; i<m; ++i)
		for (j=i+1; j<=m; ++j)
			if (count[i].tot > count[j].tot 
				|| ( count[i].tot==count[j].tot && count[i].id>count[j].id) )
			{
				count[0]=count[i];
				count[i]=count[j];
				count[j]=count[0];
			}
	for (i=1;i<=m;i++)
		printf("%s\n", ss[count[i].id], count[i].tot);	
	
	return 0;
}

// start at 19:05 